package com.algorithms.absdatatypes;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.algorithms.datatypes.GraphNodeImpl;

public class Heap<T extends Comparable,D> {
	Node<T,D>[] dataArray;
	int size;

	public Node<T,D>[] getDataArray() {
		return dataArray;
	}

	public void setDataArray(Node<T,D>[] dataArray) {
		this.dataArray = dataArray;
	}

	public Heap(Node<T,D>[] input) {

		dataArray = input;
		size = input.length;
	}
	public Heap() {
		Class<?> ct = Node.class;
		dataArray = (Node<T,D>[]) Array.newInstance(ct,1);
		size = 1;
	}
	public Heap(T[] input) {
		List<Node<T,D>> list = new ArrayList<Node<T,D>>();
		Node<T,D> node =null;
		for (T key :input)
		{
			 node = new GraphNodeImpl<T,D>(key,(D)key);
			list.add(node);
		}
		Class<?> ct = node.getClass();
		dataArray = (Node<T,D>[]) Array.newInstance(ct,list.size());
		dataArray=list.toArray(dataArray);
		/*
		dataArray =  list.toArray();*/
		size = input.length;
	}
	public void insertData(Node<T,D> data) {
		// Convert to a arraylist
		if(data!=null)
		{
			
		List<Node<T,D>> list = new ArrayList<Node<T,D>>();
		for (Node<T,D> d : dataArray) {
			if(d!=null)
			list.add(d);
		}
		list.add(data);
		dataArray = list.toArray(dataArray);
		// decrease key
		decreaseKey(dataArray.length - 1, data);
		}

	}
	public void insertData(T key) {
		Node<T,D> data = new GraphNodeImpl<T,D>(key,(D)key);
		// Convert to a arraylist
		List<Node<T,D>> list = new ArrayList<Node<T,D>>();
		for (Node<T,D> d : dataArray) {
			list.add(d);
		}
		list.add(data);
		dataArray = list.toArray(dataArray);
		// decrease key
		decreaseKey(dataArray.length - 1, data);

	}
	
	public Node<T,D> extractMin() {
		Node<T,D> root =dataArray[0];
		dataArray[0]=dataArray[dataArray.length-1];
		dataArray[dataArray.length-1]= root;
		// Convert to a arraylist
		LinkedList<Node<T,D>> list = new LinkedList<Node<T,D>>();
		for (Node<T,D> d : dataArray) {
			list.add(d);
		}
		list.removeLast();
		Class<?> ct = root.getClass();
		Node<T,D>[] newDarray = (Node<T,D>[]) Array.newInstance(ct,list.size());
		int count=0;
		for (Node<T,D> data : list) {
			newDarray[count++]=data;
		}
		dataArray = newDarray;
		// decrease key
		if(dataArray.length >0)
		minheapify(0,dataArray.length-1);
		return root;
	}

	 public int findKeyinHeap(Node<T,D> key)
	 {
		 for(int i=0;i < dataArray.length;i++)
		 {
			 if(key.getKey().compareTo(dataArray[i].getKey())==0 && dataArray[i].equals(key.getData()))
				 return i;
		 }
		 return -1;
	 }
	 public Node<T,D> findNodeForKeyinHeap(T key)
	 {
		 //Node<T,D> returnData = null;
		 for(int i=0;i < dataArray.length;i++)
		 {
			 if(key.compareTo(dataArray[i].getKey())==0)
			 {
				
				 return dataArray[i];
			 }
		 }
		 return null;
	 }
	public void maxheapify(int rootIndex, int range) {
		int lIndex = leftIndex(rootIndex);
		int rIndex = rightIndex(rootIndex);
		Node<T,D> largest = dataArray[rootIndex];
		int ex = rootIndex;
		if (lIndex < range
				&& dataArray[lIndex].getKey().compareTo(largest.getKey()) > 0) {
			largest = dataArray[lIndex];
			ex = lIndex;
		}
		if (rIndex < range
				&& dataArray[rIndex].getKey().compareTo(largest.getKey()) > 0) {
			largest = dataArray[rIndex];
			ex = rIndex;
		}
		// exchange root with largest
		if (ex != rootIndex) {
			dataArray[ex] = dataArray[rootIndex];
			dataArray[rootIndex] = largest;
			maxheapify(ex, range);
		}
	}

	public void buildmaxheap() {
		for (int i = size / 2 - 1; i >= 0; i--) {
			maxheapify(i, size);
		}
	}

	public void heapSort() {
		buildmaxheap();
		for (int i = size - 1; i >= 0; i--) {
			Node<T,D> root = dataArray[0];
			dataArray[0] = dataArray[i];
			dataArray[i] = root;
			System.out.println(root);
			maxheapify(0, i);
		}
	}

	public void buildminheap() {
		for (int i = size / 2 - 1; i >= 0; i--) {
			minheapify(i, size);
		}
	}

	public void minheapify(int rootIndex, int range) {
		int lIndex = leftIndex(rootIndex);
		int rIndex = rightIndex(rootIndex);
		System.out.println(dataArray.length);
		Node<T,D> smallest = dataArray[rootIndex];
		int ex = rootIndex;
		if (lIndex < range
				&& dataArray[lIndex].getKey().compareTo(smallest.getKey()) < 0) {
			smallest = dataArray[lIndex];
			ex = lIndex;
		}
		if (rIndex < range
				&& dataArray[rIndex].getKey().compareTo(smallest.getKey()) < 0) {
			smallest = dataArray[rIndex];
			ex = rIndex;
		}
		// exchange root with smallest
		if (ex != rootIndex) {
			dataArray[ex] = dataArray[rootIndex];
			dataArray[rootIndex] = smallest;
			minheapify(ex, range);
		}
	}

	public void decreaseKey(int loc, Node<T,D> key) {
		/*
		 * if(dataArray[loc].doubleValue() < key.doubleValue()) { throw new
		 * RuntimeException("Key is rather increased"); }
		 */
		int i = loc;
		while (i > 0
				&& key.getKey().compareTo(dataArray[parentIndex(i)].getKey())<0) {
			Node<T,D> temp = dataArray[parentIndex(i)];
			dataArray[parentIndex(i)] = key;
			dataArray[i] = temp;
			i = parentIndex(i);
		}

	}
	
   public Node<T,D> getMin()
   {
	   return this.dataArray[0];
   }
	private int parentIndex(int i) {
		int ret;
		if (i % 2 > 0)
			ret = i / 2;
		else
			ret = i / 2 - 1;

		return ret;
	}

	private int leftIndex(int i) {
		return 2 * i + 1;
	}

	private int rightIndex(int i) {
		return 2 * i + 2;
	}
}
